/**
 * 文件名：shellSort.ts
 * 文件描述：实现希尔排序
 * */

function shellSort(arr: number[]): number[] {
	// 获取到数组长度
	const length = arr.length;

	// 设置间隔
	let gap = Math.floor(length / 2);

	while (gap >= 1) {
		// 通过gap进行分组，对元素进行插入排序
		// i = gap是灵魂，gap是对应分组的第二个元素
		for (let i = gap; i < length; i++) {
			let temp = arr[i];
			let j = i;
			// [0,gap - 1]的元素是属于各个分组的第一个元素，gap刚刚好是第一个分组的第二个元素
			while (arr[j - gap] > temp && j > gap - 1) {
				arr[j] = arr[j - gap];
				j -= gap;
			}
			arr[j] = temp;
		}

		gap = Math.floor(gap / 2); // 更新间隔
	}

	return arr;
}
